package ds.tree;

import java.util.LinkedList;

public class LevelOrderTraversalQueueImpl {

	private LinkedList<TreeNode> queue = null;

	
	private static class TreeNode{
		int value;
		TreeNode left = null;
		TreeNode right = null;
		
		TreeNode(int val){
			this.value = val;
		}
		
		public String toString(){
			return String.valueOf(value);
		}
	}
	public LevelOrderTraversalQueueImpl(){
		this.queue = new LinkedList<TreeNode>();
	}
	
	public void levelOrderTraversal(TreeNode node){
		queue.add(node);
		while(!queue.isEmpty()){
			TreeNode n = queue.poll();
			System.out.print(n+ " ");
			if(n.left != null)
			queue.add(n.left);
			if(n.right != null)
			queue.add(n.right);
		}
		
	}
	private static TreeNode tree(){
		TreeNode A = new TreeNode(1);
		TreeNode B = new TreeNode(2);
		TreeNode C = new TreeNode(3);
		TreeNode D = new TreeNode(4);
		TreeNode E = new TreeNode(5);
		
		A.left = B;
		A.right = C;
		B.left = D;
		B.right = E;
		
		return A;
	}
	
	public static void main(String[] args) {
		LevelOrderTraversalQueueImpl queueImpl = new LevelOrderTraversalQueueImpl();
		queueImpl.levelOrderTraversal(tree());
	}

}
